package 递归与分治算法.汉诺塔问题;

/**
 * @Project: data-structure-and-algorithms
 * @Package: 递归与分治算法.汉诺塔问题
 * @ClassName: TowerOfHanoi
 * @Author: zhouyihe
 * @Date: 2025/11/17 15:46
 * @Description:
 */
public class TowerOfHanoi {

    public static void main(String[] args) {
        int n = 3; // 圆盘数量
        System.out.println("汉诺塔问题 - " + n + " 个圆盘:");
        hanoi(n, 'A', 'B', 'C');
        System.out.println("完成移动，共需要 " + ((1 << n) - 1) + " 步");
    }

    /**
     * 汉诺塔问题
     * 递归结构：问题可以分解为更小规模的相同问题
     * 时间复杂度：O(2^n)，n是圆盘数量
     * 空间复杂度：O(n)，递归栈的深度
     * 确定性：无论如何操作，最少需要2^n-1步才能完成
     *
     * @param n
     * @param source
     * @param auxiliary
     * @param target
     */
    private static void hanoi(int n, char source, char auxiliary, char target) {
        // 只有一个圆盘时
        if (n == 1) {
            System.out.println("移动圆盘 1 从 " + source + " 到 " + target);
            return;
        }

        // 将第n-1个圆盘从源柱移动到辅助柱
        hanoi(n - 1, source, target, auxiliary);

        // 将第n个圆盘从源柱移动到目标柱
        System.out.println("移动圆盘 " + n + " 从 " + source + " 到 " + target);

        // 将第n-1个圆盘从辅助柱移动到目标柱
        hanoi(n - 1, auxiliary, source, target);
    }

    /**
     * 广义汉诺塔：有四根柱子的情况
     * @param n
     * @param source
     * @param auxiliary1
     * @param auxiliary2
     * @param target
     */
    private static void fourPegHanoi(int n, char source, char auxiliary1, char auxiliary2, char target) {
        if (n == 0) {
            return;
        }

        if (n == 1) {
            System.out.println("移动圆盘 1 从 " + source + " 到 " + target);
            return;
        }

        // 计算最优划分点k
        int k = (int) Math.sqrt(2 * n + 1);

        // 将上面的n-k个圆盘从源柱移动到第一个辅助柱
        fourPegHanoi(n - k, source, auxiliary2, target, auxiliary1);

        // 将下面的k个圆盘从源柱移动到目标柱（使用经典三柱汉诺塔算法）
        hanoi(k, source, auxiliary2, target);

        // 将之前移到第一个辅助柱的n-k个圆盘移动到目标柱
        fourPegHanoi(n - k, auxiliary1, source, auxiliary2, target);
    }
}
